package leetcode.editor.cn.q1_300.q50;

import leetcode.editor.cn.util.tree.btree.BTreeUtil;
import leetcode.editor.cn.util.tree.btree.TreeNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @author qidi
 * @date 2021-12-28 10:34:54
 */
class Q0094_BinaryTreeInorderTraversal {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> result = new ArrayList<>();

            Deque<TreeNode> stack = new ArrayDeque<>();

            while (!stack.isEmpty() || root != null) {
                if (root != null) {
                    stack.push(root);
                    root = root.left;
                } else {
                    root = stack.pop();
                    result.add(root.val);
                    root = root.right;
                }
            }

            return result;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0094_BinaryTreeInorderTraversal().new Solution();
        TreeNode node;
//        node = BTreeUtil.getInstance().generateFromArray(new Integer[]{1, 2, 3, 4, 5, 6, 7});
        node = BTreeUtil.getInstance().generateFromArray(new Integer[]{1, null, 2, 3});
        System.out.println(solution.inorderTraversal(node));
    }
}